/**
 * 两数之和 时间复杂度O(N)
 * @param nums
 * @param target
 * @returns
 */
function twoSum(nums: number[], target: number): number[] {
  const map = new Map()
  for (let i = 0; i < nums.length; i++) {
    if (map.has(target - nums[i])) {
      return [map.get(target - nums[i]), i]
    }
    map.set(nums[i], i)
  }
}

const nums = [3, 2, 4]
const target = 6

console.log(twoSum(nums, target))
// output [1, 2]

/**
 * 两数之和-暴力循环
 * 时间复杂度O(N^2)
 * @param nums
 * @param target
 * @returns
 */
function twoSum1(nums: number[], target: number): number[] {
  const len = nums.length
  for (let i = 0; i < len; i++) {
    for (let j = i + 1; j < len; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j]
      }
    }
  }
}

/**
 * 已排序数组，计算两个数之和-双指针
 * @param nums
 * @param target
 * @returns
 */
function sortTwoSum(nums, target) {
  let left = 0
  let right = nums.length - 1
  while (left < right) {
    const sum = nums[left] + nums[right]
    if (sum < target) {
      left++
    } else if (sum > target) {
      right--
    } else {
      return [left, right]
    }
  }
}
